//给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。 
//
// 示例: 
//
// 输入: n = 4, k = 2
//输出:
//[
//  [2,4],
//  [3,4],
//  [2,3],
//  [1,2],
//  [1,3],
//  [1,4],
//] 
// Related Topics 数组 回溯 
// 👍 612 👎 0


package service.week02.leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

//Java：组合
public class P77Combinations {
    public static void main(String[] args) {
        Solution solution = new P77Combinations().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> combine(int n, int k) {
            Deque<Integer> deque = new ArrayDeque<>();
            List<List<Integer>> res = new ArrayList<>();
            dfs(1, n, k, deque, res);
            return res;
        }

        public void dfs(int cur, int n, int k, Deque<Integer> deque, List<List<Integer>> res) {
            //递归终止条件 超过k 或者剩余数不足k
            if (deque.size() > k || deque.size() + (n - cur + 1) < k) {
                return;
            }
            if (cur == n + 1) {

                res.add(new ArrayList<>(deque));

                return;
            }

            //加入当前
            deque.addLast(cur);
            dfs(cur + 1, n, k, deque, res);
            deque.removeLast();
            //不加入
            dfs(cur + 1, n, k, deque, res);
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}